package leetcode.l0616;

/**
 * @author Retain
 * @date 2021/6/16 19:05
 */
public class Medium_石子游戏_877 {

    /**
     * dp[i][j]表示从i到j最大可以赢对方多少分
     * i>j不存在
     * i=j直接拿
     * i<j dp[i][j]=max(piles[i]-dp[i+1][j],piles[j]-dp[i][j-1])
     * @param piles
     * @return
     */
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                dp[i][j] = Math.max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
            }
        }

        return dp[0][n-1] > 0;
    }
}
